package 力扣;

public class x的平方根69 {
    /*这个算法会时间比较耗时*/
    public static int mySqrt(int x) {
        if (x<=0){
            if (x==0)
                return 0;
            else
              return -1;
        }
         for (int i=1;i<=x;i++){
             if (i*i>=x){
                 if (i*i==x)
                     return i;
                 else
                    return i-1;
             }
         }
         return -1;
    }
    /*一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt。
    可以利用二分查找在 0 ~ x 之间查找 sqrt。*/
    public  static int mySqrt2(int x){
        if (x<=1){
            return x;
        }
        int i=x;
        int low=0;int high=i-1;
        int mid=low+(high-low)/2;
        while (low<=high){
            if (mid*mid<x){//当数太大的时候会造成溢出，即出现65537
                low=mid+1;
            }else if (mid*mid==x){
                return mid;
            }else
                high=mid-1;
            mid=low+(high-low)/2;
        }
        return mid-1;

    }
    public  static int mySqrt3(int x){
        if (x <= 1) {
            return x;
        }
        int l = 1, h = x;
        while (l <= h) {
            int mid = l + (h - l) / 2;
            int sqrt = x / mid;//巧妙地将乘法改为除法，避免了溢出
            if (sqrt == mid) {
                return mid;
            } else if (mid > sqrt) {
                h = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return h;
    }

    public static void main(String[] args) {
        /*int []nums=new int[]{1,2,3,4,5,6,7,8};
        int i = binarySearch(nums, 5);
        System.out.println(i);*/
        System.out.println(mySqrt2(100000));
        System.out.println(mySqrt3(10000000));
        System.out.println(2^31);
    }

    /**
     * 二分查找的源代码
     * @param nums
     * @param key
     * @return
     */
    public static int binarySearch(int[] nums, int key) {
        int l=0;int h=nums.length-1;
        while (l<=h){
//            int mid = (l + h) / 2;可能有加法的溢出问题
            int mid=l + (h - l) / 2;// h - l 不会出现加法溢出问题
            if (nums[mid]==key){
                return mid;
            }else if (nums[mid]>key){
                h=mid-1;
            }else {
                l=mid+1;
            }
        }
        return -1;
    }
}
